W poniższym raporcie omówione zostaną wyniki różnych algorytmów analizy skupień zastosowanych na danych benchmarkowych. Dane zostały pobrane ze strony https://github.com/gagolews/clustering_benchmarks_v1.
Większość zbiorów ma 2 lub 3 wymiary. Ułatwia to zwizualizowanie wyników klasteryzacji przez poszczególne metody, jednakże pobrany również zbiór to dużo większych wymiarach.
Zbiory zostały pobrane w postaci plików .data oraz .labels0. Następnie za pomocą funkcji zdefiniowanych w pliku Padpy_generowanie_csv.py wyniki benchmarków zostały zapisane w pliku .csv, z którego będziemy korzystać tworząc ten raport. Za pomocą wyżej wspomnianych funkcji wygenerowane zostały również wykresy jako pliki .png, które będą zawarte w poniższym raporcie.
Do porównania jakości klasteryzacji wykorzystane zostały następujące metody:
algorytmy hierarchiczne - z wykorzystaniem funkcji AgglomerativeClustering z następującymi parametrami:
algorytm DBSCAN (Density-Based Spatial Clustering of Applications with Noise) - klasteryzacja dla najbardziej zagęszczonych punktów
Porównanie zostanie również działanie zaimplementowanego algorytmu spektralnego dla różnych parametrów M, równych: 1%, 5%, 10% lub 30% wszystkich obserwacji w danym zbiorze. W przypadku, gdy dla żadnej z tych wartości parametru metoda nie działała dobrze, została również sprawdzona metoda z ręcznie wprowadzoną wartością M, niezależnie od wielkości zbioru.
Jakość wyników poszczególnych algorytmów zostanie porównana za pomocą:
indeksu Fowlkesa–Mallowsa (FMI) - zwraca podobieństwo między zwracanymi klastrami, obliczany za pomocą wzoru: $$\sqrt{\frac{TP}{TP+FP} \cdot \frac{TP}{TP+FN}}$$
skorygowanego indeksu Randa (ARI) - jest to indeks Randa skorygowany o prawdopodobieństwo przydziału punktów do danego klastra, gdzie indeks Randa jest wyrożony nastepującą furmułą: $$\sqrt{\frac{TP+TN}{TP+FP+FN+TN}}$$
gdzie:
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from IPython.display import Image
import plotly.graph_objects as go
def wykres1(index_ARI, index_FMI, names, plot_title):
"""
funkcja przyjmuje argumenty:
index_ARI - type: list of floats, lista wspolczynnikow ARI
index_FMI - type: list of floats, lista wspolczynnikow FMI
names - type: list of strings, lista z nazwami metod uzytych do porownania
plot_title - type: string, tytul wykresu
funkcja rysuje wykres slupkowy interaktywny za pomoca pakietu Plotly
"""
fig = go.Figure(data=[
go.Bar(name='Fowlkes-Mallows index', x=names, y=np.round(index_FMI,4)),
go.Bar(name='Adjusted Rand index', x=names, y=np.round(index_ARI,4))],
)
hovertemplate = "<b>%{x}</b><br>" +\
"Index value: %{y}<br>"
fig.update_traces(
hovertemplate=hovertemplate
)
fig.update_layout(barmode="group",
title= {
'text' : '<b>'+ plot_title +'</b>',
'x':0.5,
'xanchor': 'center'})
fig.show()
return
plots_title = "Wykres wartości indeksów FMI i ARI dla poszczególnych algorytmów klasteryzacji"
def tabelka(names, index_ARI, index_FMI, w=1050, h=350):
"""
Funkcja przyjmuje argumenty:
index_ARI - type: list of floats, lista wspolczynnikow ARI
index_FMI - type: list of floats, lista wspolczynnikow FMI
names - type: list of strings, lista z nazwami metod uzytych do porownania
"""
fig = go.Figure(data=[go.Table(header=dict(values=['Method', 'Fowlkes-Mallows index',
'Adjusted Rand index']),
cells=dict(values=[names, np.round(index_FMI,4), np.round(index_ARI,4)]))
])
fig.update_layout(width=w, height=h)
fig.show()
return
def tabelka_std(names, index_ARI, index_FMI,index_ARI_std,index_FMI_std, w=1000, h=350):
"""
Funkcja przyjmuje argumenty:
index_ARI - type: list of floats, lista wspolczynnikow ARI
index_FMI - type: list of floats, lista wspolczynnikow FMI
names - type: list of strings, lista z nazwami metod uzytych do porownania
index_ARI_std - type: list of floats, lista wspolczynnikow ARI dla zmiennych zestandaryzowanych
index_FMI_std - type: list of floats, lista wspolczynnikow FMI dla zmiennych zestandaryzowanych
"""
fig = go.Figure(data=[go.Table(header=dict(values=['Method', 'FMI', 'ARI',
'FMI for standarized variables', 'ARI for standarized variables']),
cells=dict(values=[names, np.round(index_FMI,4), np.round(index_ARI,4),
np.round(index_FMI_std,4), np.round(index_ARI_std,4)]))
])
fig.update_layout(width=w, height=h)
fig.show()
return
Zdefiniujmy ścieżkę do wczytywanych plików oraz funkcję która będzie wczytywała pliki .csv i podawała informacje o wymiarach zbioru i liczbie klastrów.
path1 = r"C:\Users\patry\OneDrive\Pulpit\Zdalne pw\Python - PadPy\Projekt_23_dane_benchmarkowe"
def wczytaj(path, file_name):
zbior = pd.read_csv(path + '\\' + file_name, sep=';')
print("Wymiary zbioru: ", zbior["Shape"][0])
print("Liczba klastrów", zbior["Number of clusters"][0])
return zbior
line = wczytaj(path1, 'line_2.csv')
Widzimy, że zbiór line jest relatywnie niewielki. Odgórnie podzielony jest na dwa klastry, podział wygląda następująco:
Image(path1 + '\\' + "line_2_main.png", width=500, height=500)
Porównajmy działanie poszczególnych metod klasteryzacji na omawianym zbiorze.
wykres1(list(line['Adjusted Rand index']), list(line['Fowlkes-Mallows index']), list(line['Method']), plots_title)
Na powyższym wykresie widać, że równoważny podział reprezentują metody:
Pozostałe metody mają ujemne wartości współczynnika ARI, zatem działają nieefektywnie. Widać to też na poniższych wykresach reprezentujących zbior podzielony na klastry przez poszczególne algorytmy.
Image(path1 + '\\' + 'line_2_builtin_methods.png', width=1000, height=500)
Image(path1 + '\\' + "line_2_spectral_algorithm.png", width=1000, height=500)
Zbadamy wpływ standaryzacji zmiennych na działanie algorytmów.
line_std = wczytaj(path1, 'line_std_2.csv')
tabelka_std(list(line['Method']), list(line['Adjusted Rand index']), list(line['Fowlkes-Mallows index']),
list(line_std['Adjusted Rand index']),list(line_std['Fowlkes-Mallows index']), w=1000, h=650)
Widzimy, że standaryzacja nie ma żadnego wpływu na wartości indeksów (możliwe, że pobrane zbiory były już zestandaryzowane).
Zbiór parabolic ma 2 pliki z etykietami (labels0, labels1), które dzielą zbiór odpowiednio na 2 i 4 klastry. Wczytajmy najpierw wyniki benchmarków dla piewszej z etykiet.
parabolic = wczytaj(path1, 'parabolic_2.csv')
parabolic2 = wczytaj(path1, 'parabolic_4.csv')
Widzimy, że zbiór jest większy od poprzedniego, ma on 1000 obserwacji. Zobaczmy na wykresie jego odgórny podział na 2 i 4 części.
Image(path1 + '\\' + "parabolic_two_labels.png", width=1000, height=500)
Widzimy, że klastry przypominają 'kawałki' paraboli. Porównajmy najpierw jakość podziału na 2 części zwrócony przez poszczególne metody z podziałem narzuconym z etykiet.
wykres1(list(parabolic['Adjusted Rand index']), list(parabolic['Fowlkes-Mallows index']), list(parabolic['Method']), plots_title)
W tym przypadku żaden z algorytmów nie zwrócił równoważnego podziału z podziałem odgórnym. Największe współczynniki ARI i FMI mają metody Genie oraz DBSCAN. Zobaczmy jak to wygląda na wykresach.
Image(path1 + '\\' + 'parabolic_2_builtin_methods.png', width=1000, height=500)
Image(path1 + '\\' + 'parabolic_2_spectral_algorithm.png', width=1000, height=500)
Obserwując wykresy warto zauważyć, że algorytm DBSCAN samodzielnie znajduję liczbę klastrów i w tym przypadku utworzył klaster koloru fioletowego reprezentujący szum (co jest ogólną zaletą tego algorytmu).
Zbadamy różnicę w klasteryzacji dla poszczególnych metod w przypadku, gdy zmienne są zestandaryzowane.
parabolic_std = wczytaj(path1, 'parabolic_std_2.csv')
tabelka_std(list(parabolic['Method']), list(parabolic['Adjusted Rand index']), list(parabolic['Fowlkes-Mallows index']),
list(parabolic_std['Adjusted Rand index']),list(parabolic_std['Fowlkes-Mallows index']), w=1000, h=650)
W tym przypadku możemy zauważyc znaczny spadek wartości skorygowanego indeksu Randa dla algorytmu spektralnego oraz dla metody DBSCAN. Na pozostałe metody standaryzacja nie miała większego wpływu.
Analogicznie porównajmy indeksy ARI oraz FMI, a także zwizualizujmy podział zbiorór przez analizowane metody.
wykres1(list(parabolic2['Adjusted Rand index']), list(parabolic2['Fowlkes-Mallows index']), list(parabolic2['Method']), plots_title)
Image(path1 + '\\' + 'parabolic_4_builtin_methods.png', width=1000, height=500)
Image(path1 + '\\' + 'parabolic_4_spectral_algorithm.png', width=1000, height=500)
Wartości współczynników, że najbliżej oryginalnego podziału są zbiory wynikowe algorytmu spektralnego, jednakże analizując wykresy można mieć zdecydowanie inne wrażenie. Wizualnie odgórny podział najbardziej przypominają klastry algorytmu Genie.
Mimo wszystko w tym przypadku żaden algorytm nie działa zbyt dobrze.
spiral = wczytaj(path1, 'spiral_3.csv')
Image(path1 + '\\' + "spiral_3_main.png", width=500, height=500)
Sprawdźmy jakość podziału zbioru spiral na trzy klastry.
tabelka(list(spiral['Method']), list(spiral['Adjusted Rand index']), list(spiral['Fowlkes-Mallows index']), h=500)
Image(path1 + '\\' + 'spiral_3_builtin_methods.png', width=1000, height=500)
Image(path1 + '\\' + 'spiral_3_spectral_algorithm.png', width=1000, height=500)
Image(path1 + '\\' + "spiral_spectral_10__3_main.png", width=500, height=500)
Na podstawie wartości współczynników z tabeli oraz wizualizacji widzimy, że najlepszy podział zbioru zwracają:
spiral_std = wczytaj(path1, 'spiral_std_3.csv')
tabelka_std(list(spiral['Method']), list(spiral['Adjusted Rand index']), list(spiral['Fowlkes-Mallows index']),
list(spiral_std['Adjusted Rand index']),list(spiral_std['Fowlkes-Mallows index']),w=1000, h=750)
W tym przypadku po standaryzacji zmiennych, możemy zauważyć znaczną poprawę działania metody DBSCAN, której podział stał się równoważny do podziału oryginalnego. Może to zaskakiwać biorąc pod uwagę, że w kilku poprzednich zbiorach algorytm ten po standaryzacji działał zdecydowanie gorzej.
Jednak w tym przypadku po standaryzacji po standaryzacji punkty w jednym klastrze są jeszcze gęściej położone, co mogło zaważyć na poprawie jakości algorytmu, który właśnie bazuje na gęstości położonych punktów.
engytime0 = wczytaj(path1, 'engytime2_v0.csv')
engytime1 = wczytaj(path1, 'engytime2_v1.csv')
Image(path1 + '\\' + "engytime_two_labels.png", width=1000, height=500)
Widzimy, że zbiór engytime oryginalnie został podzielony na dwa klastry, ale na dwa różne sposoby. Podział na wykresie po prawej stronie jest jednak bardziej intuicyjny i to nim się zajmiemy.
wykres1(list(engytime1['Adjusted Rand index']), list(engytime1['Fowlkes-Mallows index']), list(engytime1['Method']), plots_title)
Image(path1 + '\\' + 'engytime_2_builtin_methods.png', width=1000, height=500)
Image(path1 + '\\' + "engytime_spectral_1%__2_main.png", width=500, height=500)
Widzimy, że w tym przypadku zbiór został dosyć dobrze podzielony metodą spektralną oraz Genie. W odróżnieniu od poprzednich zbiorów, w tym przypadku dobre podziały zwróciły: algorytm k-srednich oraz algorytm hierarchiczny bazujący na przeciętnej odległości. Jednakże patrząc na kształ zbioru, wyniki nie powinny dziwić, ponieważ wszystkie punkty są położone gęsto, zatem lepiej zadziałają metody oparte na średnich odległościach.
Ciekawy, niemniej jednak logiczny rozumiejąc jego działanie, jest również podział oparty na algorytmie DBSCAN, który oddzielił punkty będące szumem od jednego głównego klastra stanowiącego większość obserwacji w zbiorze.
zigzag4 = wczytaj(path1, 'zigzag_noisy_4.csv')
zigzag6 = wczytaj(path1, 'zigzag_noisy_6.csv')
Image(path1 + '\\' + "zigzag_noisy_two_labels.png", width=1000, height=500)
Widzimy, że według etykiet z plikków .labels zbiór jest podzielony na 4 lub na 6 klastrów. Zauważmy, że w każdym podziale, jeden z klastrów stanowi szum. Sprawdzimy więc, jak dobrze poszczególne metody go wykrywają. Bardziej intuicyjny jest podział na 4 klastry, więc ten omówimy.
tabelka(names = list(zigzag4['Method']), index_ARI = list(zigzag4['Adjusted Rand index']),
index_FMI = list(zigzag4['Fowlkes-Mallows index']), w=1050, h=500)
Image(path1 + '\\' + 'zigzag_noisy_4_builtin_methods.png', width=1000, height=500)
Image(path1 + '\\' + 'zigzag_noisy_4_spectral_algorithm.png', width=1000, height=500)
Niestety w tym przypadku żaden algorytm nie działa efektywnie. Najwyższe współczynniki ARI oraz FMI mają metody Genie oraz spektralna dla M=5% obserwacji. Jednakże nawet te podziały nie wykrywają szumu, a pozostałe klastry również są dalekie od oryginalnych.
zigzag4_std = wczytaj(path1, 'zigzag_noisy_std_4.csv')
tabelka_std(list(zigzag4['Method']), list(zigzag4['Adjusted Rand index']), list(zigzag4['Fowlkes-Mallows index']),
list(zigzag4_std['Adjusted Rand index']),list(zigzag4_std['Fowlkes-Mallows index']), w=1000, h=650)
W tym przypadku standaryzacja zmiennych niewiele poprawiła w żadnym z podziałów. Może to być spowodowane tym, że przedziały wartości obu współrzędnych są symetryczne i ich krańce nie są duże (-2,2). Jak wiemy standaryzacja jest szczególnie ważna w przypadku zmiennych różniących się rzędem wielkości albo chociaż kilkukrotnie, co nie zdarza się w tym zbiorze.
square = wczytaj(path1, 'square_2.csv')
Image(path1 + '\\' + "square_2_main.png", width=500, height=500)
Widzimy, że dwuwymiarowy zbiór square oryginalnie jest podzielony na 2 klastry, co jest zgodne z wykresem punktowym.
wykres1(list(square['Adjusted Rand index']), list(square['Fowlkes-Mallows index']), list(square['Method']), plots_title)
Image(path1 + '\\' + "square_2_builtin_methods.png", width=1000, height=500)
Image(path1 + '\\' + "square_2_spectral_algorithm.png", width=1000, height=500)
Dla tego zbioru już możemy znaleźć podziały równoważne z oryginalnym, w szczególności są to te wygenerowane dzięki metodom:
square_std = wczytaj(path1, 'square_std_2.csv')
wykres1(list(square['Adjusted Rand index']), list(square['Fowlkes-Mallows index']), list(square['Method']), plots_title)
wykres1(list(square_std['Adjusted Rand index']), list(square_std['Fowlkes-Mallows index']), list(square_std['Method']),
plots_title + "<br> po standaryzacji zmiennych </br>")
Sytuacja jest podobna do tej z poprzedniego punktu. Z tego powodu, że przedziały wartości poszczególnych współrzędnych są symetryczne, a ich krańce są podobnej wielkości, standaryzacja niewiele zmienia w podziałach zbioru. Jedynie widoczna jest poprawa współczynników dla metody spektralnej z parametrem M=1% wszystkich obserwacji.
isolation = wczytaj(path1, 'isolation_3.csv')
Zbiór ma relatywnie dużo obserwacji, więc z powodu dużej złożoności obliczeniowej algorytmu spektralnego, nie zastosujemy go w tym podpunkcie (duża złożoność wynika z zaimplementowanego algorytmu przeszukiwania w głąb, która korzysta z rekurencji).
tabelka(names = list(isolation['Method']), index_ARI = list(isolation['Adjusted Rand index']),
index_FMI = list(isolation['Fowlkes-Mallows index']))
Widzimy, że podziały uzyskane za pomocą algorytmów Genie i hierarchicznego z parametrem single linkage są równoważne z oryginalnym podziałem. Zobaczmy to na wykresach:
Image(path1 + '\\' + "isolation_3_builtin_methods.png", width=1000, height=500)
W tym przypadku, biorąc pod uwagę poprzednie podpunkty, również standaryzacja niewiele zmieni wartości indeksów dla każdej z metod, ponieważ przedziały wartości współrzędnych są symetryczne i równej długości. Pokazują to dane poniższej tabeli.
isolation_std = wczytaj(path1, 'isolation_std_3.csv')
tabelka_std(list(isolation['Method']), list(isolation['Adjusted Rand index']), list(isolation['Fowlkes-Mallows index']),
list(isolation_std['Adjusted Rand index']),list(isolation_std['Fowlkes-Mallows index']), w=1000, h=500)
chainlink = wczytaj(path1, 'chainlink_2.csv')
Image(path1 + '\\' + "chainlink_2_main.png", width=500, height=500)
Widzimy, że zbiór chainlink składa się z dwóch klastrów, których punkty na wykresie tworzą pierścienie, każdy z nich przechodzi przez wnętrze drugiego. Podobnie jak dla danych dwuwymiarowych, będziemy porównywać indeksy FMI oraz ARI dla poszczególnych metod oraz badać wpływ standaryzacji na ich wartości.
wykres1(list(chainlink['Adjusted Rand index']), list(chainlink['Fowlkes-Mallows index']), list(chainlink['Method']), plots_title)
Image(path1 + '\\' + "chainlink_2_bulitin_methods.png", width=1000, height=500)
Image(path1 + '\\' + "chainlink_2_spectral_algorithm.png", width=1000, height=500)
Widzimy, że dla tego zbioru mamy kilka metod tworących podziały równoważne oryginalnemu. Są to:
W tym przypadku obserując zakresy wartości poszczególnych zmiennych, również można wysunąć hipotezę, że standaryzacja każdej z nich nie będzie miała większego wpływu na podział zbioru przez różne metody. Potwierdzają to dane w poniższej tabeli.
chainlink_std = wczytaj(path1, 'chainlink_std_2.csv')
tabelka_std(list(chainlink['Method']), list(chainlink['Adjusted Rand index']), list(chainlink['Fowlkes-Mallows index']),
list(chainlink_std['Adjusted Rand index']),list(chainlink_std['Fowlkes-Mallows index']), w=1000, h=650)
atom = wczytaj(path1, 'atom_2.csv')
Image(path1 + '\\' + "atom_2_main.png", width=500, height=500)
Widzimy, że zbiór oryginalnie jest podzielony na dwa klastry, a punkty z każdego dnich tworzą kształ kul, z których jedna jest wewnątrz drugiej.
tabelka(names = list(atom['Method']), index_ARI = list(atom['Adjusted Rand index']),
index_FMI = list(atom['Fowlkes-Mallows index']), w=1050, h=500)
Image(path1 + '\\' + "atom_3_bulitin_methods.png", width=1000, height=500)
Image(path1 + '\\' + "atom_3_spectral_algorithm.png", width=1000, height=500)
Możemy zauważyć na podstawie powyższej tabeli oraz wykresów, że zdecydowanie najlepsze podziały zbioru generują metody:
atom_std = wczytaj(path1, 'atom_std_2.csv')
Porównajmy wartości indeksów przed i po standaryzacji
wykres1(list(atom['Adjusted Rand index']), list(atom['Fowlkes-Mallows index']), list(atom['Method']), plots_title)
wykres1(list(atom_std['Adjusted Rand index']), list(atom_std['Fowlkes-Mallows index']), list(atom_std['Method']),
plots_title + "<br> po standaryzacji zmiennych </br>")
Widzimy, że dzięki standaryzacji zdecydowanie poprawiła się jakość podziału generowanego przez metodę DBSCAN. Pozostałe wartości indeksów niewiele się zmieniły.
sonar = wczytaj(path1, 'sonar_2.csv')
sonar_std = wczytaj(path1, 'sonar_std_2.csv')
Widzimy, że zbiór sonar ma 60 zmiennych i jest podzielony na 2 klastry. Porównamy wartości indeksów ARI oraz FMI dla poszczególnych metod. Z oczywistych powodów wizualizacja podziału jest niewykonalna.
tabelka_std(list(sonar['Method']), list(sonar['Adjusted Rand index']), list(sonar['Fowlkes-Mallows index']),
list(sonar_std['Adjusted Rand index']),list(sonar_std['Fowlkes-Mallows index']), w=1000, h=650)
Widzimy, że dla powyżej zdefiniowanego zbioru, wszystkie metody zwracają podział, który nie jest zbliżony do oryginalnego, co obrazują bliskie zera wartości indeksu ARI
Na podstawie 10 pobranych zbiorów benchmarkowych i wygenerowanych z nich wyników w postaci plików .csv oraz .png możemy wysunąć następujące wnioski:
Dodatkowo zaletą metody DBSCAN jest brak konieczności odgórnie zdefiniowanej ilości klastrów, co może pomóc kiedy nie jesteśmy w stanie zwizualizować danych lub nie potrafimy jednoznacznie stwierdzić liczby klastrów.